We start by presenting some basic concepts to facilitate the understanding of the mechanisms that are presented further on.
Packets
Data sources typically split the data they send into small units known as packets. A packet consists of a header and a payload. The great majority of packets carried by commercial networks nowadays are so-called Internet protocol (IP) packets, which means they comply to the format specified in IETF RFC 791 (J. Postel: “Internet Protocol”, Internet Engineering Task Force STD 5, September 1981) as updated by various subsequent amendments. IP ensures the packets are correctly transmitted from the source to the destination. IP is a connectionless protocol—that means each packet carries sufficient information for any IP router to be able to forward it towards its destination without having had to previously set up any per-connection state in the router. Each packet could take a different route to reach the destination. In practice the routing mechanisms on the Internet mean that this seldom happens (unless there is some form of equipment failure).
Encapsulation and Tunnelling
It is common for the payload of each packet to contain or encapsulate a number of further headers that are defined by various communication protocols. When a packet reaches the destination computer specified in its IP header, the destination strips off the IP header and uses the next header to determine which process within the computer should handle the resulting payload. Further headers encapsulated within that might tell the receiving process 30 which session the packet belongs to and other information, such as what the source computer is asking the destination computer to do.
Packet networks invariably use this technique called header encapsulation to wrap the packet itself within a further header called a frame header. For instance, in order to transmit an IP packet to a router at the other end of an Ethernet link, the IP packet is encapsulated within an Ethernet header addressed to the router. This is further discussed in RFC1042 (J. Postel & J. Reynolds: “A Standard for the Transmission of IP Datagrams over IEEE 802 Networks”, Internet Engineering Task Force Request for comments 1042, February 1988). This means an Ethernet header is pre-pended to the IP packet and some further Ethernet information is added to the end of the packet. In general, encapsulation may only involve pre-pending without post-pending. When the destination router addressed in the outermost Ethernet header is reached, at the end of the Ethernet segment of the path, it will recognise that the Ethernet frame is addressed to itself and decapsulate the payload of the Ethernet frame by stripping off the Ethernet header and footer. It will then inspect the IP header of the resulting packet and look up the destination IP address in its IP routing table. This routing lookup will give the router the link layer address to use to reach the next IP router and the output port to forward the packet out of in order to reach it. If, for instance, this output port uses Multiprotocol Label Switching (MPLS) technology, discussed further in RFC 3031 (E. Rosen, A. Viswanathan and R. Callon: “Multiprotocol Label Switching Architecture”, IETF RFC3031, January 2001), the router will encapsulate the IP packet in an MPLS header, and a label will be included that the next MPLS label switched router (LSR) will use to forward the MPLS frame onwards towards subsequent LSRs.
IP packets can be encapsulated within further IP headers rather than the headers of lower layer protocols such as Ethernet or MPLS. This technique is called tunnelling, because it forces the inner IP packet to take a path via an intermediate machine with the destination IP address in the outer header. This intermediate machine strips off (decapsulates) the outer IP header and discovers another IP packet inside. It then forwards this to the destination IP address given in the new outermost header, which was previously the inner header.
Tunnelling is not confined to IP packets. It is common for Ethernet frames to contain further Ethernet frames (termed MAC in MAC) and MPLS headers often encapsulate further MPLS headers (termed a label stack).
The methods described below are equally applicable to any network technology that transmits data in packet-like or frame-like messages, whether IP, IEEE 802 (Ethernet), MPLS, or other similar technologies.
Re-Feedback
One of the functions of a packet header such as the header of an IP packet is to accumulate information about the path it traverses on its way from the sender to the receiver. For instance, the time-to-live (TTL) field is decremented at every IP node or the explicit congestion notification (ECN) field is probabilistically marked if the packet experiences congestion (see next section). This path information allows nodes on the path to monitor characteristics of the path experienbed so far (the upstream path). Mechanisms exist or have been proposed to allow the receiver to feed back this information to the sender. ECN is discussed further in RFC 3168 (K. Ramakrishnan, S. Floyd, & D. Black: “The Addition of Explicit Congestion Notification (ECN) to IP”, Internet Engineering Task Force Request for comments 3168, September 2001).
International application WO 2005/096566 describes a mechanism called re-feedback, whereby the source re-inserts into the forward data path this information fed back to it by the receiver that had accumulated along the whole path. The sender may reinsert this information using a separate field in the packet header to that used to accumulate the original path metric or alternatively, it may initialise the value of the metric in the original field to a value that reflects the feedback it receives.
Re-feedback is also discussed in the article “Policing Congestion Response in an Internetwork Using Re-Feedback” by B. Briscoe, A. Jacquet, C. Cairano-Gilfedder, A. Salvatori, A. Soppera, & M. Koyabe (Proc. ACM SIGCOMM'05, Computer Communication Review 35(4):277-288, ACM Press, August 2005).
Any node along the path may then monitor the characteristics of the whole path at least a round trip ago. Given any node can already monitor the characteristics of the upstream path, it can subtract this from the re-inserted whole path information to calculate an expectation of the characteristics of the downstream path (the rest of the path still to be traversed by packets it forwards).
International application WO 2005/109783 describes a mechanism to detect that a source is persistently understating a characteristic of the path in a flow of packets, and sanction the flow accordingly to make it in the source's interests to comply with the required behaviour that assures the integrity of the re-inserted feedback and the original feedback.
Distributed Bandwidth Sharing and Congestion
Data traversing the Internet follows a path between a series of routers, controlled by various routing protocols. Each router seeks to move the packet closer to its final destination. If too much traffic traverses the same router in the network, the router can become congested and packets start to experience excessive delays whilst using that network path. If sources persist in sending traffic through that router it could become seriously overloaded (congested) and even drop traffic (when its buffers overflow). If sources still persist in sending traffic through this bottleneck it could force more routers to become congested, and if the phenomenon keeps spreading, that can lead to a congestion collapse for the whole Internet—which occurred regularly in the mid-1980s.
The solution to that problem has been to ensure that sources take responsibility for the rate at which they send data over the Internet by implementing congestion control mechanisms. Sources monitor feedback from the receiver of the metric that characterises path congestion in order to detect when the path their data is following is getting congested, in which case they react by reducing their throughput—while they may slowly increase their rate when there is no sign of the path becoming congested.
The typical path characterisation metrics that sources monitor are the average roundtrip time (RTT) for the data path, the variance of the roundtrip time (jitter) and the level of congestion on the path. The congestion is one of the parameters controlling the rate adaptation of a source sending data over a congested path.
The congestion level can be signalled either implicitly (through congested routers dropping packets when their buffers overflow or to protect themselves) or explicitly (through mechanisms such as explicit congestion notification—see next subsection). Currently the most common option is implicit signalling. Historically, routers would drop packets when they got completely saturated (which happens when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called Droptail. Random Early Detection (RED) is an improvement where routers monitor the average queue length in their buffer and when the average queue is higher than a given threshold, the router starts to drop packets with a probability which increases with the excess length of the queue over the threshold. It is widely used in today's Internet because it allows sources to react more promptly to incipient congestion and it keeps queues from growing unnecessarily long. Sources using TCP are able to detect losses, because a packet loss causes a gap in the numbered sequence of bytes transferred. Whenever a TCP source detects a loss, it is meant to halve its data transmission rate, which alleviates the congestion on the router at the bottleneck.
RED is discussed further in the article “Random Early Detection Gateways for Congestion Avoidance” by S. Floyd & V. Jacobson (IEEE/ACM Transactions on Networking, Vol 1-4 (397-413) August 1993).
Explicit Congestion Notification in the Internet Protocol
Explicit Congestion Notification (ECN) further improves on RED by using a two-bit ECN field in the IP header to signal congestion. It runs the same algorithm as RED, but instead of dropping a packet, it sets its ECN field to the Congestion Experienced (CE) codepoint. The ECN standard requires the receiver to echo any congestion mark signalled in the data; for instance, a TCP receiver sets the Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets as if the packet has been dropped for the purpose of its rate control. In turn the source then reacts to the congestion by halving its transmission rate and notifies the receiver of this using the Congestion Window Reduced (CWR) codepoint in the TCP header.
The four values of the two-bit ECN field in the IP header are:                Non ECT, which signifies that the packet belongs to a flow that doesn't support ECN        ECT(0) and ECT(1), which signify that the packet belongs to a flow that supports ECN but that upstream routers haven't had to mark the packet.        Congestion Experienced (CE) which signals that a packet has experienced incipient congestion.Encapsulation of Explicit Congestion Notification (ECN)        
The ECN field is defined within the IP header and in the headers of some lower layer protocols, such as the MPLS shim header. Further information on this is provided in RFC5129 (Davie, Briscoe & Tay: “Explicit Congestion Marking in MPLS”, Internet Engineering Task Force Request for comments rfc5129.txt, January 2008). Therefore when one IP header is encapsulated by another, or by a lower layer header such as the MPLS shim header, standard procedures must be followed to specify how a marking applied to the ECN field in the outer header will propagate to the inner header when it is decapsulated. Otherwise as an outer header is discarded, ECN markings in the outer header would also be discarded before they reached the ultimate destination at the address specified in the inner header. These rules are specified in RFC3168 for IP, RFC4301 for secure encapsulation of IP packets (IPsec) and RFC5129 for MPLS. Slightly modified rules are in the process of being standardised by the IETF—further information on this is available in “Tunnelling of Explicit Congestion Notification” by B. Briscoe (Internet Engineering Task Force Internet Draft draft-ietf-tsvwg-ecn-tunnel-08.txt, March 2010) (Work in progress), Appendix C of which describes how to measure the contribution to congestion introduced only by routers encountered between the encapsulating ingress and the decapsulating egress of a tunnel.
A document entitled “ECN Interactions with IP Tunnels” by Floyd, Ramakrishnan & Black (draft-floyd-ecn-tunnels-01.txt, October 2000) discusses how ECN should be propagated across tunnel endpoints. It also discusses various anomalous behaviours that might be introduced in a tunnel to pervert the measurement of end-to-end congestion.
Re-ECN
Re-ECN is an example of a system that utilises re-feedback to provide upstream and downstream congestion information throughout the network. It is similar to ECN but uses an extra unused bit in the packet header. This bit is combined with the two-bit ECN field to create four extra codepoints.
Re-ECN is discussed further in “Re-ECN: Adding Accountability for Causing Congestion to TCP/IP” by B. Briscoe, A. Jacquet, T. Moncaster & A. Smith (IETF Internet Draft draft-briscoe-tsvwg-re-ecn-tcp-08, September 2009). The current re-ECN specification is one candidate for a new standardisation activity being undertaken by the IETF. The final standard defined by the IETF may differ in detail from this proposed specification. The present embodiment is described with respect to this protocol proposal, without any intent to imply the invention is limited solely to the details of this one particular protocol proposal.
The simplest way to understand the protocol is to think of each packet as having a different colour flag (codepoint). At the start of a flow, a green flag (referred to as FNE or “feedback not established”) is used to indicate that the sender does not have sufficient knowledge of the path. Green flags are also used when the sender is unsure about the current state of the path.
By default packets are marked with grey flags. If they encounter congestion during their progress through the network the ECN “congestion experienced” (CE) marking applied by the congested router will be termed a red flag. The destination will feed back a count of the number of red flags it has seen. For every red flag it is informed of, the sender should mark an equivalent number of bytes it sends in a subsequent packet or packets with a black flag. The black flag re-echoes or reinserts the congestion feedback back into the forward-travelling stream of packets, hence the name re-ECN. These black flags will not be modified once they are set by the sender. There is a small possibility that a black packet will in turn be marked red by a congested router, but the codepoints are chosen so that it is still possible to tell the packet was originally marked as black—such packets are described as coloured black-red.
At any intermediate node the upstream congestion is given by the proportion of red flagged bytes to total bytes. Thus the continually varying congestion level is effectively encoded in a stream of packets by interpreting the stream of red or non-red markings as a unary encoding of ones or zeroes respectively. Similarly, the congestion level of the whole path is encoded as a stream of black or non-black markings in the IP header. The expected downstream congestion from an intermediate IP-aware node can then be estimated from the difference between the respective proportions of black and red markings, as described in International application WO2006/079845.
If IP packets with red and black re-ECN markings have been encapsulated by an additional outer header or headers, further red ECN markings may be applied to the outer header. When this outer header or headers is or are removed, any red markings will be propagated to the forwarded packet by standard decapsulation techniques. During the process of encapsulation, the black markings in the inner header remain unchanged. Therefore, once an original inner IP packet has been decapsulated, the proportions of black and red markings can be measured and compared, even if the red markings were added while the packet was encapsulated.
Discussion of Prior Art/Known Techniques
It has been discussed how re-feedback can be used to measure any general characteristic of both the upstream and downstream paths of data packets passing through a node in a data network. Thus an intermediate node can establish a characteristic property of all three of: i) the path so far experienced; ii) the whole path; and iii) the rest of the path still to be experienced.
It has also been discussed how measurements of these three aspects of a path can be made for the specific case of congestion, using the specific instantiation of re-feedback referred to above and elsewhere as re-ECN.
Further, various ways to measure the contribution to specific path metrics introduced only by the nodes encountered between the encapsulating ingress and the decapsulating egress of a tunnel have been described. For instance, the article “Tunnelling of Congestion Notification” discussed above indicates that it is possible to measure the contribution to congestion introduced only by the routers encountered between the encapsulating ingress and the decapsulating egress of a tunnel. This technique generalises to any form of encapsulation, such as IP in MPLS (RFC5129), not just IP in IP.
Similarly, it is possible for the egress node of a tunnel to measure the number of forwarding hops experienced by a tunnelled packet by comparing the time to live (TTL) field of the outer header with that of the inner.